
class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> myhash;
        for(const auto& e : wordDict){
            myhash.insert(e);
        }
        int len = s.length();
        vector<bool> dp(len+1,false); //dp[i]代表的是前i个字符是否可以被字典中的字符串代替
        dp[0] = true; //s中前0个字符串默认可以被字典中的字符串代替
        for(int i = 1;i < len + 1;++i)
        {
            for(int j = 0;j < i;++j)
            {
                if(dp[j] && myhash.count(s.substr(j,i-j)))
                {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[len];
    }
};